/*
    
哈希表是一种常用的数据结构，用于快速插入、查找和删除操作。它使用哈希函数将键映射到哈希表中的位置，从而减少搜索范围，提升操作效率。

哈希表的基本概念
哈希函数：将键值转换为哈希表的索引。
冲突处理：当两个不同的键产生相同的哈希值时，称之为哈希冲突。常用的冲突处理策略包括链地址法和开放地址法。
负载因子：表明哈希表的负载程度，通常用于动态调整哈希表的大小。
用C语言实现哈希表
以下是一个使用链地址法（Separate Chaining）的哈希表示例。在这种方法中，哈希表的每个桶（bucket）是一个链表，可以容纳多个冲突的元素。
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 哈希表的节点
typedef struct HashNode {
    char* key;  // 键
    int value;  // 值
    struct HashNode* next;  // 下一个节点
} HashNode;

// 哈希表
typedef struct HashTable {
    int size;  // 哈希表大小
    HashNode** buckets;  // 桶数组
} HashTable;

// 创建哈希表
HashTable* createHashTable(int size) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    if (table) {
        table->size = size;
        table->buckets = (HashNode**)malloc(sizeof(HashNode*) * size);
        for (int i = 0; i < size; i++) {
            table->buckets[i] = NULL;
        }
    }
    return table;
}

// 简单哈希函数
int hashFunction(const char* key, int tableSize) {
    int hash = 0;
    while (*key) {
        hash = (hash * 31 + *key) % tableSize;  // 乘法散列
        key++;
    }
    return hash;
}

// 创建新节点
HashNode* createNode(const char* key, int value) {
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    if (node) {
        node->key = strdup(key);  // 复制键字符串
        node->value = value;
        node->next = NULL;
    }
    return node;
}

// 插入到哈希表
void insert(HashTable* table, const char* key, int value) {
    int index = hashFunction(key, table->size);
    HashNode* current = table->buckets[index];
    HashNode* prev = NULL;

    // 查找键是否已存在
    while (current != NULL && strcmp(current->key, key) != 0) {
        prev = current;
        current = current->next;
    }

    if (current == NULL) {  // 键不存在，插入新节点
        HashNode* newNode = createNode(key, value);
        if (prev == NULL) {
            table->buckets[index] = newNode;
        } else {
            prev->next = newNode;
        }
    } else {  // 键已存在，更新值
        current->value = value;
    }
}

// 在哈希表中查找
int search(HashTable* table, const char* key, int* value) {
    int index = hashFunction(key, table->size);
    HashNode* current = table->buckets[index];

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {  // 找到目标键
            *value = current->value;
            return 1;  // 返回成功
        }
        current = current->next;  // 继续查找
    }

    return 0;  // 未找到
}

// 删除哈希表中的节点
void delete(HashTable* table, const char* key) {
    int index = hashFunction(key, table->size);
    HashNode* current = table->buckets[index];
    HashNode* prev = NULL;

    while (current != NULL && strcmp(current->key, key) != 0) {
        prev = current;
        current = current->next;
    }

    if (current == NULL) {  // 未找到键
        return;
    }

    if (prev == NULL) {  // 删除头节点
        table->buckets[index] = current->next;
    } else {
        prev->next = current->next;
    }

    free(current->key);  // 释放节点
    free(current);
}

// 释放哈希表
void freeHashTable(HashTable* table) {
    for (int i = 0; i < table->size; i++) {
        HashNode* current = table->buckets[i];
        while (current != NULL) {
            HashNode* next = current->next;
            free(current->key);
            free(current);
            current = next;
        }
    }

    free(table->buckets);
    free(table);
}

// 测试哈希表
int main() {
    HashTable* table = createHashTable(10);

    insert(table, "apple", 10);
    insert(table, "banana", 20);
    insert(table, "orange", 30);

    int value;
    if (search(table, "banana", &value)) {
        printf("Found banana with value: %d\n", value);
    } else {
        printf("Banana not found\n");
    }

    delete(table, "banana");

    if (search(table, "banana", &value)) {
        printf("Found banana with value: %d\n", value);
    } else {
        printf("Banana not found\n");
    }

    freeHashTable(table);  // 释放哈希表

    return 0;
}
